#include <bits/stdc++.h>

using namespace std;

/**********************************************
 *
 * 建模：
 * 使用数字大小表示 煎饼的大小，为了方便起见，
 * 当煎饼数为n时候，采用1~n表示煎饼的大小
 * 如此 pancakes 属于1~n的全排列
 *
 * ************************************************/

class Pancake {
public:
    Pancake(int size, bool is_facedown = true) {
        this->size = size;
        this->is_facedown = is_facedown;
    }
    void flip() {
        is_facedown ^= 1;
    }
    bool is_facedown;
    int size;
};

class Solution {
public:
    Solution(vector<Pancake> &pancakes) {
        this->pancakes = pancakes;
        cnt = 0;
    }
    int SortPancakes() {
        for (int _size = pancakes.size(); _size > 1; _size--) {
            if (pancakes[_size - 1].size == _size && pancakes[_size - 1].is_facedown == true) {
                continue; // 已经在所在位置了 且 头朝下
            }
            flip(search(_size)); // 翻转到头

            // 翻转到尾 check一下是否是 burned朝下,如果朝下 翻转到上
            if (pancakes[0].is_facedown) {
                cnt++;
                pancakes[0].flip();
                // print();
            }
            flip(_size - 1);
        }
        if (!pancakes[0].is_facedown) {
            cnt++;
            // print();
            pancakes[0].flip();
        }
        return cnt;
    }

    void print() {
        cout << "now, pancakes are:\n";
        for (Pancake &p : pancakes) {
            cout << "(size:" << p.size << ",face:" << (p.is_facedown ? "down" : "up") << ")\n";
        }
        cout << "cnt of flip is " << cnt << endl << endl;
    }
private:
    vector<Pancake> pancakes;
    int cnt;

    void flip(int ed) {
        // 翻转范围为 [0,ed]

        if (ed == 0) return; // 长度为1 不要翻转

        cnt++; // 翻转次数+1

        int mid = (ed + 1 >> 1);
        for (int i = 0; i < mid; i++) {
            swap(pancakes[i], pancakes[ed - i]);
            pancakes[i].flip();
            pancakes[ed - i].flip();
        }
        if (!(ed % 2))
            pancakes[mid].flip();

        // print();

    }

    int search(int target) {
        for (int i = 0; i < pancakes.size(); i++) {
            if (pancakes[i].size == target)
                return i;
        }
        return -1;
    }


};


int main() {
    vector<Pancake>pc{ Pancake(3),Pancake(2,false),Pancake(4),Pancake(1) };
    Solution *s = new Solution(pc);
    s->print();
    s->SortPancakes();
    s->print();
    //system("pause");
    return 0;
}
